package com.arron.algorithm.leetcodetop100.回溯.排列and组合and子集;

import java.util.*;

public class 全排列II {

    List<List<Integer>> resList;
    boolean[] flag;
    //    Set<String> combine;
    public List<List<Integer>> permuteUnique(int[] nums) {
//        combine =new HashSet<>();

        resList = new ArrayList<>();

        List<Integer> res = new ArrayList<>();
        flag = new boolean[nums.length];
        Arrays.sort(nums);
        permute(nums,res);
        return resList;
    }

    public void permute(int[] nums,List<Integer> res){



        if (res.size() == nums.length){

            resList.add(new ArrayList<>(res));
            return;
        }


        for (int i = 0; i < nums.length; i++) {
            //该元素已被选择，剪枝
            if (flag[i]) continue;
            //前面元素还没被选择的时候，如果两个值相等，则剪枝
            if ( i>0 && nums[i] == nums[i-1] && !flag[i-1]) continue;
            res.add(nums[i]);
            flag[i] = true;
            permute(nums,res);
            flag[i] = false;
            res.remove(res.size()-1);
        }

    }

    public static void main(String[] args) {

        全排列II combine = new 全排列II();
        int[] nums =new int[]{1,1,2};
        combine.permuteUnique(nums);

    }
}
